package org.apache.lucene.geo3d;
   
   /*
    * Licensed to the Apache Software Foundation (ASF) under one or more
    * contributor license agreements.  See the NOTICE file distributed with
    * this work for additional information regarding copyright ownership.
    * The ASF licenses this file to You under the Apache License, Version 2.0
    * (the "License"); you may not use this file except in compliance with
    * the License.  You may obtain a copy of the License at
   *
   *     http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  
  import java.util.ArrayList;
  import java.util.BitSet;
  import java.util.List;
  
  /**
   * GeoConvexPolygon objects are generic building blocks of more complex structures.
   * The only restrictions on these objects are: (1) they must be convex; (2) they must have
   * a maximum extent no larger than PI.  Violating either one of these limits will
   * cause the logic to fail.
   *
   * @lucene.experimental
   */
  public class GeoConvexPolygon extends GeoBasePolygon {
    /** The list of polygon points */
    protected final List<GeoPoint> points;
    /** A bitset describing, for each edge, whether it is internal or not */
    protected final BitSet isInternalEdges;
  
    /** A list of edges */
    protected SidedPlane[] edges = null;
    /** The set of notable points for each edge */
    protected GeoPoint[][] notableEdgePoints = null;
    /** A point which is on the boundary of the polygon */
    protected GeoPoint[] edgePoints = null;
    /** Tracking the maximum distance we go at any one time, so to be sure it's legal */
    protected double fullDistance = 0.0;
    /** Set to true when the polygon is complete */
    protected boolean isDone = false;
    
    /**
     * Create a convex polygon from a list of points.  The first point must be on the
     * external edge.
     *@param planetModel is the planet model.
     *@param pointList is the list of points to create the polygon from.
     */
    public GeoConvexPolygon(final PlanetModel planetModel, final List<GeoPoint> pointList) {
      super(planetModel);
      this.points = pointList;
      this.isInternalEdges = new BitSet();
      done(false);
    }
  
    /**
     * Create a convex polygon from a list of points, keeping track of which boundaries
     * are internal.  This is used when creating a polygon as a building block for another shape.
     *@param planetModel is the planet model.
     *@param pointList is the set of points to create the polygon from.
     *@param internalEdgeFlags is a bitset describing whether each edge is internal or not.
     *@param returnEdgeInternal is true when the final return edge is an internal one.
     */
    public GeoConvexPolygon(final PlanetModel planetModel, final List<GeoPoint> pointList, final BitSet internalEdgeFlags,
                            final boolean returnEdgeInternal) {
      super(planetModel);
      this.points = pointList;
      this.isInternalEdges = internalEdgeFlags;
      done(returnEdgeInternal);
    }
  
    /**
     * Create a convex polygon, with a starting latitude and longitude.
     * Accepts only values in the following ranges: lat: {@code -PI/2 -> PI/2}, lon: {@code -PI -> PI}
     *@param planetModel is the planet model.
     *@param startLatitude is the latitude of the first point.
     *@param startLongitude is the longitude of the first point.
     */
    public GeoConvexPolygon(final PlanetModel planetModel, final double startLatitude, final double startLongitude) {
      super(planetModel);
      points = new ArrayList<>();
      isInternalEdges = new BitSet();
      points.add(new GeoPoint(planetModel, startLatitude, startLongitude));
    }
  
    /**
     * Add a point to the polygon.
     * Accepts only values in the following ranges: lat: {@code -PI/2 -> PI/2}, lon: {@code -PI -> PI}
     *
     * @param latitude       is the latitude of the next point.
     * @param longitude      is the longitude of the next point.
     * @param isInternalEdge is true if the edge just added with this point should be considered "internal", and not
     *                       intersected as part of the intersects() operation.
    */
   public void addPoint(final double latitude, final double longitude, final boolean isInternalEdge) {
     if (isDone)
       throw new IllegalStateException("Can't call addPoint() if done() already called");
     if (isInternalEdge)
       isInternalEdges.set(points.size() - 1);
     points.add(new GeoPoint(planetModel, latitude, longitude));
   }
 
   /**
    * Finish the polygon, by connecting the last added point with the starting point.
    *@param isInternalReturnEdge is true if the return edge (back to start) is an internal one.
    */
   public void done(final boolean isInternalReturnEdge) {
     if (isDone)
       throw new IllegalStateException("Can't call done() more than once");
     // If fewer than 3 points, can't do it.
     if (points.size() < 3)
       throw new IllegalArgumentException("Polygon needs at least three points.");
 
     if (isInternalReturnEdge)
       isInternalEdges.set(points.size() - 1);
 
     isDone = true;
     
     // Time to construct the planes.  If the polygon is truly convex, then any adjacent point
     // to a segment can provide an interior measurement.
     edges = new SidedPlane[points.size()];
     notableEdgePoints = new GeoPoint[points.size()][];
 
     for (int i = 0; i < points.size(); i++) {
       final GeoPoint start = points.get(i);
       final GeoPoint end = points.get(legalIndex(i + 1));
       final double distance = start.arcDistance(end);
       if (distance > fullDistance)
         fullDistance = distance;
       final GeoPoint check = points.get(legalIndex(i + 2));
       final SidedPlane sp = new SidedPlane(check, start, end);
       //System.out.println("Created edge "+sp+" using start="+start+" end="+end+" check="+check);
       edges[i] = sp;
       notableEdgePoints[i] = new GeoPoint[]{start, end};
     }
     createCenterPoint();
   }
 
   /** Compute a reasonable center point.
    */
   protected void createCenterPoint() {
     // In order to naively confirm that the polygon is convex, I would need to
     // check every edge, and verify that every point (other than the edge endpoints)
     // is within the edge's sided plane.  This is an order n^2 operation.  That's still
     // not wrong, though, because everything else about polygons has a similar cost.
     for (int edgeIndex = 0; edgeIndex < edges.length; edgeIndex++) {
       final SidedPlane edge = edges[edgeIndex];
       for (int pointIndex = 0; pointIndex < points.size(); pointIndex++) {
         if (pointIndex != edgeIndex && pointIndex != legalIndex(edgeIndex + 1)) {
           if (!edge.isWithin(points.get(pointIndex)))
             throw new IllegalArgumentException("Polygon is not convex: Point " + points.get(pointIndex) + " Edge " + edge);
         }
       }
     }
     edgePoints = new GeoPoint[]{points.get(0)};
   }
 
   /** Compute a legal point index from a possibly illegal one, that may have wrapped.
    *@param index is the index.
    *@return the normalized index.
    */
   protected int legalIndex(int index) {
     while (index >= points.size())
       index -= points.size();
     return index;
   }
 
   @Override
   public boolean isWithin(final double x, final double y, final double z) {
     for (final SidedPlane edge : edges) {
       if (!edge.isWithin(x, y, z))
         return false;
     }
     return true;
   }
 
   @Override
   public GeoPoint[] getEdgePoints() {
     return edgePoints;
   }
 
   @Override
   public boolean intersects(final Plane p, final GeoPoint[] notablePoints, final Membership... bounds) {
     //System.err.println("Checking for polygon intersection with plane "+p+"...");
     for (int edgeIndex = 0; edgeIndex < edges.length; edgeIndex++) {
       final SidedPlane edge = edges[edgeIndex];
       final GeoPoint[] points = this.notableEdgePoints[edgeIndex];
       if (!isInternalEdges.get(edgeIndex)) {
         //System.err.println(" non-internal edge "+edge);
         // Edges flagged as 'internal only' are excluded from the matching
         // Construct boundaries
         final Membership[] membershipBounds = new Membership[edges.length - 1];
         int count = 0;
         for (int otherIndex = 0; otherIndex < edges.length; otherIndex++) {
           if (otherIndex != edgeIndex) {
             membershipBounds[count++] = edges[otherIndex];
           }
         }
         if (edge.intersects(planetModel, p, notablePoints, points, bounds, membershipBounds)) {
           //System.err.println(" intersects!");
           return true;
         }
       }
     }
     //System.err.println(" no intersection");
     return false;
   }
 
   @Override
   public void getBounds(Bounds bounds) {
     super.getBounds(bounds);
 
     // Add all the points
     for (final GeoPoint point : points) {
       bounds.addPoint(point);
     }
 
     // Add planes with membership.
     for (int edgeIndex = 0; edgeIndex < edges.length; edgeIndex++) {
       final SidedPlane edge = edges[edgeIndex];
       // Construct boundaries
       final Membership[] membershipBounds = new Membership[edges.length - 1];
       int count = 0;
       for (int otherIndex = 0; otherIndex < edges.length; otherIndex++) {
         if (otherIndex != edgeIndex) {
           membershipBounds[count++] = edges[otherIndex];
         }
       }
       bounds.addPlane(planetModel, edge, membershipBounds);
     }
   }
 
   @Override
   protected double outsideDistance(final DistanceStyle distanceStyle, final double x, final double y, final double z) {
     double minimumDistance = Double.MAX_VALUE;
     for (final GeoPoint edgePoint : points) {
       final double newDist = distanceStyle.computeDistance(edgePoint, x,y,z);
       if (newDist < minimumDistance) {
         minimumDistance = newDist;
       }
     }
     for (int edgeIndex = 0; edgeIndex < edges.length; edgeIndex++) {
       final Plane edgePlane = edges[edgeIndex];
       final Membership[] membershipBounds = new Membership[edges.length - 1];
       int count = 0;
       for (int otherIndex = 0; otherIndex < edges.length; otherIndex++) {
         if (otherIndex != edgeIndex) {
           membershipBounds[count++] = edges[otherIndex];
         }
       }
       final double newDist = distanceStyle.computeDistance(planetModel, edgePlane, x, y, z, membershipBounds);
       if (newDist < minimumDistance) {
         minimumDistance = newDist;
       }
     }
     return minimumDistance;
   }
 
   @Override
   public boolean equals(Object o) {
     if (!(o instanceof GeoConvexPolygon))
       return false;
     GeoConvexPolygon other = (GeoConvexPolygon) o;
     if (!super.equals(other))
       return false;
     if (!other.isInternalEdges.equals(isInternalEdges))
       return false;
     return (other.points.equals(points));
   }
 
   @Override
   public int hashCode() {
     int result = super.hashCode();
     result = 31 * result + points.hashCode();
     return result;
   }
 
   @Override
   public String toString() {
     return "GeoConvexPolygon: {planetmodel=" + planetModel + ", points=" + points + "}";
   }
 }